#include <stdio.h>
#include <stdlib.h>
#define n 10			/* n: number of buckets */

void bucket_sort(double *a, int len)
{
  int i, j, k, bn;		/* bn: bucket number */
  int index[n];		        /* index[i]: insert a[] to b[][index[] */
  double count[n], *b[n];	/* count[i]: length of bucket[i] */

  for (i = 0; i < n; i++)
    count[i] = index[i] = 0;
  for (i = 0; i < len; i++)
    count[((int)(a[i] * 10)) == 10 ? 9 : (int)(a[i] * 10)]++; /* put '1' in b[9] */
  for (i = 0; i < n; i++)
    b[i] = (double *)malloc(sizeof(double) * count[i]);
  for (i = 0; i < len; i++) {	/* insert a[i] to a bucket */
    bn = (int)(a[i] * 10);
    b[bn][index[bn]++] = a[i];
  }
  for (i = k = 0; i < n; i++)
    for (j = 0; j < count[i]; j++)
      a[k++] = b[i][j];
  for(i = 0; i < n; i++)
    free(b[i]);
}
